/**
 * Created by IntelliJ IDEA.
 * User: Roman
 * Date: 11.09.12
 * Time: 22:00
 * To change this template use File | Settings | File Templates.
 */
public class Solver {

    private Node solvedBoard = null;
    private boolean isSolvable = false;

    private class Node implements Comparable {
        Board item;
        Node previous;
        int moves = 0;

        private Node(Board item, Node previous, int moves) {
            this.item = item;
            this.previous = previous;
            this.moves = moves;
        }

        @Override
        public int compareTo(Object o) {
            Node x = (Node) o;
            if (x.item.manhattan() + x.moves > this.item.manhattan() + this.moves) {
                return -1;
            } else if (x.item.manhattan() + x.moves == this.item.manhattan() + this.moves)
                return 0;
            else
                return 1;
        }
    }

    public Solver(Board initial) {
        Node initialNode = new Node(initial, null, 0);
        Node twinNode = new Node(initial.twin(), null, 0);
        MinPQ<Node> solvingInitialPQ = new MinPQ<Node>();
        MinPQ<Node> solvingTwinPQ = new MinPQ<Node>();

        solvingInitialPQ.insert(initialNode);
        for (Board board : initial.neighbors()) {
            solvingInitialPQ.insert(new Node(board, initialNode, initialNode.moves + 1));
        }

        for (Board board : twinNode.item.neighbors()) {
            solvingTwinPQ.insert(new Node(board, twinNode, twinNode.moves + 1));
        }
        initialNode = solvingInitialPQ.delMin();
        twinNode = solvingTwinPQ.delMin();

        while (initialBoardOrTwinBoardNotSolved(initialNode, twinNode)) {
            for (Board board : initialNode.item.neighbors()) {
                if (initialNode.previous != null)
                    if (!board.equals(initialNode.previous.item))
                        solvingInitialPQ.insert(new Node(board, initialNode, initialNode.moves + 1));
            }
            for (Board board : twinNode.item.neighbors()) {
                if (twinNode.previous != null)

                    if (!board.equals(twinNode.previous.item))
                        solvingTwinPQ.insert(new Node(board, twinNode, twinNode.moves + 1));
            }
            initialNode = solvingInitialPQ.delMin();
            twinNode = solvingTwinPQ.delMin();
        }

        if (initialNode.item.isGoal()) {
            solvedBoard = initialNode;
            isSolvable = true;
        }

    }

    private boolean initialBoardOrTwinBoardNotSolved(Node initialNode, Node twinNode) {
        return (!initialNode.item.isGoal()) && (!twinNode.item.isGoal());
    }


    public boolean isSolvable() {
        return isSolvable;
    }

    public int moves() {
        if (!isSolvable)
            return -1;
        return solvedBoard.moves;
    }

    public Iterable<Board> solution() {
        Stack<Board> solution = null;
        if (isSolvable()) {
            solution = new Stack<Board>();
            Node iterator = solvedBoard;
            do {
                solution.push(iterator.item);
                iterator = iterator.previous;
            } while (iterator != null);
        }
        return solution;
    }

    public static void main(String[] args) {
        // create initial board from file
        In in = new In(args[0]);
        int N = in.readInt();
        int[][] blocks = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                blocks[i][j] = in.readInt();
        Board initial = new Board(blocks);

        // solve the puzzle
        Solver solver = new Solver(initial);

        // print solution to standard output
        if (!solver.isSolvable())
            StdOut.println("No solution possible");
        else {
            StdOut.println("Minimum number of moves = " + solver.moves());
            for (Board board : solver.solution())
                StdOut.println(board);
        }
    }

}